package com.zp.self.module.level_4_算法练习.数据结构.数组;

/**
 * @author By ZengPeng
 */
public class 力扣_136_只出现一次的数字 {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_136_只出现一次的数字().maxProfit(new int[]{2,2,1}));
        System.out.println(new 力扣_136_只出现一次的数字().maxProfit(new int[]{4,1,2,1,2}));
        System.out.println(new 力扣_136_只出现一次的数字().maxProfit(new int[]{100}));
    }

    /**
     题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
         说明：
         你的算法应该具有线性时间复杂度 O(n)。 你可以不使用额外空间来实现吗？
         示例 1:
         输入: [2,2,1]
         输出: 1

     分析：【P ❤】
         1.使用空间：可以使用Set记录出现过的数字
         2.不适用空间： 全部加起来？  先排序？时间复杂度>O(n)
                                    √不使用额外空间 则考虑异或
            --执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户

     边界值注意：
        1.
     */
    public int maxProfit(int[] nums) {
        int a=nums[0];
        for (int i = 1; i < nums.length; i++)
            a^= nums[i];
        return a;
    }
}
